package one.three.thirtyThree;

public class Deque<Item> {

	private Node<Item> first;
	private Node<Item> last;

	public boolean isEmpty() {
		return first == null;
	}

	public int size() {
		if (first != null) {
			int s = 0;
			Node<Item> c = first;
			while (c != null) {
				s++;
				c = c.next;
			}
			return s;
		}
		return 0;
	}

	public void pushHead(Item item) {
		if (first == null) {
			first = new Node<Item>();
			first.item = item;
			last = first;
		} else {
			Node<Item> newNode = new Node<Item>();
			newNode.item = item;
			newNode.next = first;
			first.pre = newNode;
			first = newNode;
		}
	}

	public void pushTail(Item item) {
		if (last == null) {
			last = new Node<Item>();
			last.item = item;
			first = last;
		} else {
			Node<Item> newNode = new Node<Item>();
			newNode.item = item;
			newNode.pre = last;
			last.next = newNode;
			last = newNode;
		}
	}

	public Item popHead() {
		if (first != null) {
			Item item = first.item;
			if (first == last) {
				last = null;
			}
			first = first.next;
			return item;
		}
		return null;
	}

	public Item popTail() {
		if (last != null) {
			Item item = last.item;
			if (first == last) {
				first = null;
			}
			last = last.pre;
			return item;
		}
		return null;
	}

	public void pushLeft(Item item) {
		pushHead(item);
	}

	public void pushRight(Item item) {
		pushTail(item);
	}

	public Item popLeft() {
		Item r = popHead();
		return r;
	}

	public Item popRight() {
		Item r = popTail();
		return r;
	}

	private static class Node<Item> {
		private Item item;
		private Node<Item> next;
		private Node<Item> pre;

		@Override
		public String toString() {
			return "[" + item + "]";
		}
	}

	public static void main(String[] args) {
		Deque<String> d = new Deque<String>();
		d.pushHead("a");
		d.pushHead("b");
		d.pushHead("c");
		System.out.println(d.size());
		while (!d.isEmpty()) {
			System.out.println(d.popHead());
		}
	}

}
